|
In computer science, the Raita algorithm is a string searching algorithm which improves the performance of Boyer-Moore-Horspool algorithm. This algorithm preprocesses the string being searched for the pattern, which is similar to Boyer-Moore string search algorithm. The searching pattern of particular sub-string in a given string is different from Boyer-Moore-Horspool algorithm. This algorithm was published by Tim Raita in 1991. == Description == Raita algorithm searches for a pattern "P" in a given text "T" by comparing each character of pattern in the given text. Searching will be done as follows. Window for a text "T" is defined as the length of "P". 1. First, last character of the pattern is compared with the rightmost character of the window. 2. If there is a match, first character of the pattern is compared with the leftmost character of the window. 3. If they match again, it compares the middle character of the pattern with middle character of the window. If everything is successful, then the original comparison starts from the second character to last but one. If there is a mismatch at any stage in the algorithm, it performs the bad character shift function which was computed in pre-processing phase. Bad character shift function is similar to the one proposed in Boyer-Moore algorithm. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Raita Algorithm」の詳細全文を読む スポンサード リンク
|